The present invention relates generally to the serialization of queues in a multi-processor environment, and more specifically, to ensuring that serialization is maintained between separate transactions while searching and/or modifying a variable length queue.
Searching and/or modifying a queue in a multi-processor environment generally requires a serialization mechanism to ensure that one central processing unit (CPU) is not making incompatible changes to the queue while another CPU is either searching the queue or also making changes to the queue.
One conventional serialization mechanism is a hardware or software locking technique, which permits a single CPU to update the queue or multiple CPUs to search the queue without updating. Another conventional serial mechanism utilizes transactional execution. A typical transactional execution implementation allows a set of instructions that search or modify a queue to appear as a single transaction with respect to other CPUs. That is, all storage accesses between the start and end of the transaction appear to be block-concurrent with respect to other CPUs, and all storage updates are either committed in their entirety once the transaction ends or none of them are committed due to a fetch or store conflict with another CPU. If a conflict occurs between two CPUs (e.g., one CPU accesses a storage area that is modified by another), the transaction is aborted for one or both CPUs. The transaction can then be retried by the CPUs.